The present invention relates to the field of data compression and decompression systems; particularly, the present invention relates to a method and apparatus for lossless and lossy encoding and decoding of data in compression/decompression systems.
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction.
In lossless compression, input symbols or intensity data are converted to output codewords. The input may include image, audio, one-dimensional (e.g., data changing spatially or temporally), two-dimensional (e.g., data changing in two spatial directions (or one spatial and one temporal dimension)), or multi-dimensional/multi-spectral data. If the compression is successful, the codewords are represented in fewer bits than the number of bits required for the uncoded input symbols (or intensity data). Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. In lossless image compression, compression is based on predictions or contexts, plus coding. The JBIG standard for facsimile compression and DPCM (differential pulse code modulationxe2x80x94an option in the JPEG standard) for continuous-tone images are examples of lossless compression for images. In lossy compression, input symbols or intensity data are quantized prior to conversion to output codewords. Quantization is intended to preserve relevant characteristics of the data while eliminating unimportant characteristics. Prior to quantization, lossy compression system often use a transform to provide energy compaction. JPEG is an example of a lossy coding method for image data.
Recent developments in image signal processing continue to focus attention on a need for efficient and accurate forms of data compression coding. Various forms of transform or pyramidal signal processing have been proposed, including multiresolution pyramidal processing and wavelet pyramidal processing. These forms are also referred to as subband processing and hierarchical processing. Wavelet pyramidal processing of image data is a specific type of multi-resolution pyramidal processing that may use quadrature mirror filters (QMFs) to produce subband decomposition of an original image. Note that other types of non-QMF wavelets exist. For more information on wavelet processing, see Antonini, M., et al., xe2x80x9cImage Coding Using Wavelet Transformxe2x80x9d, IEEE Transactions on Image Processing, Vol. 1, No. 2, April 1992; Shapiro, J., xe2x80x9cAn Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficientsxe2x80x9d, Proc. IEEE Data Compression Conference, pgs. 214-223, 1993; for information on reversible transforms, see Said, A. and Pearlman, W. xe2x80x9cReversible Image Compression via Multiresolution Representation and Predictive Codingxe2x80x9d, Dept. of Electrical, Computer and Systems Engineering, Renssealaer Polytechnic Institute, Troy, N.Y. 1993.
Compression is often very time consuming and memory intensive. It is desirable to perform compression faster and/or reduced memory when possible. Some applications have never used compression because either the quality could not be assured, the compression rate was not high enough, or the data rate was not controllable. However, the use of compression is desirable to reduce the amount of information to be transferred and/or stored.
The prior art includes compression systems for handling natural continuous-tone images. An example is the International Standard Dis. 10918-1, entitled xe2x80x9cDigital Compression and Coding of Continuous-Tone Still Imagesxe2x80x9d, CCITT recommendation T.81, commonly referred to as JPEG. The prior art also includes compression systems to handle binary/noise free/shallow pixel depth images. An example of such a system is a system conforming to the International Standard ISO/IEC 11544, entitled xe2x80x9cInformation Technology-Coded Representation of Picture and Audio Informationxe2x80x94Progressive Bi-level Image Compressionxe2x80x9d, CCITT recommendation T.82, commonly referred to as JBIG. However, the prior art lacks a system that handles both adequately. It is desirable to have such a system.
Parsers are well known in the computer science literature. A parser is responsible for assigning meaning to different parts of an object with an initially unknown structure. For example, a parser operating as part of a compiler might determine that some characters in a program file are xe2x80x9cidentifiers,xe2x80x9d other characters form reserved words, and other characters are parts of a comment. The parser is not responsible for determining what the characters xe2x80x9cmeanxe2x80x9d but only what type of subject they are a part.
Most image storage formats are single-use. That is, only a single resolution or a single quality level is available. Other image formats allow multi-use. Some prior art multi-use image formats support two or three resolution/quality choices. Other prior art multi-use image formats allow only resolution or quality to be specified, not both. It is desirable to increase the resolution and quality choices that are available.
For instance, internet World-Wide-Web servers currently provide desired information from a large body of data. Typically, a user browses many images on the screen and may decide to print a few. Unfortunately, the current state of the browsing tools leads to a fairly poor quality printout if the image was intended mainly for monitors, or an excessive browse time if the image was intended mainly for printing. Obtaining a xe2x80x9closslessxe2x80x9d image is either impossible or must be done as a completely independent download.
The present invention provides lossy and lossless compression using a transform that provides good energy compaction. The present invention provides a parser that identifies and selects parts of compressed data based onto structure, such as the frequency band and importance level, to which the entropy coded data belongs to, but does not decompress the data. The present invention provides more flexible multi-use image formats.
The present invention provides a single system that can handle both natural con-tone images and binary/noise free/shallow pixel depth images, particularly those images that contain both types of data.
A system, apparatus and method for performing compression and/or decompression is described. In one embodiment, a system comprises a wavelet style coder, a binary style coder and selection control. The wavelet style coder compresses image data using reversible embedded wavelets. The binary style color compresses image data using a binary coding scheme. The selection control selects between the wavelet style and the binary style using a histogram, such as a first order Markov values of pixels.
In one embodiment, the present invention provides an encoder that includes a memory and a forward transform operating on data in the memory such that the forward transform is computed in place in the memory.
In one embodiment, the present invention provides a system having a histogram compaction mechanism, a reversible wavelet transform, an embedded order quantizer, a context modeling mechanism, and a coder.
In one embodiment of the encoding system of the present invention, an m-ary coder, such as a Huffman coder, is used as the coder.